package org.algorithm.熊猫.DFS算法;

import org.junit.Test;

/**
 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/number-of-enclaves
 */
public class $5月5日$飞地的数量 {

    @Test
    public void test(){
        int[][] arr2 = {{0,0,0,0,0},{0,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
        System.out.println(numEnclaves(arr2));
    }

    public int numEnclaves(int[][] grid) {
        int res = 0;
        int m = grid.length, n = grid[0].length;
        //横1
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                // 然后使⽤ DFS 将岛屿淹了
                dfs(grid, 0, j);
            }
        }
        //竖1
        for (int j = 0; j < m; j++) {
            if (grid[j][0] == 1) {
                // 然后使⽤ DFS 将岛屿淹了
                dfs(grid, j, 0);
            }
        }
        //横2
        for (int j = 0; j < n; j++) {
            if (grid[m-1][j] == 1) {
                // 然后使⽤ DFS 将岛屿淹了
                dfs(grid, m-1, j);
            }
        }
        //竖2
        for (int j = 0; j < m; j++) {
            if (grid[j][n-1] == 1) {
                // 然后使⽤ DFS 将岛屿淹了
                dfs(grid, j, n-1);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    // 每发现⼀个岛屿，岛屿数量加⼀
                    res++;
                }
            }
        }
        return res;
    }

    private void dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            // 超出索引边界
            return;
        }
        if (grid[i][j] == 0) {
            // 已经是海⽔了
            return;
        }
        // 将 (i, j) 变成海⽔
        grid[i][j] = 0;
        // 淹没上下左右的陆地
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}
